//
// Created by 86131 on 2023/10/24.
//

#ifndef SHUJUJIEGUO_BALANCEDTREE_H
#define SHUJUJIEGUO_BALANCEDTREE_H

#endif //SHUJUJIEGUO_BALANCEDTREE_H
#include "SearchTree.h"
/*
 * avl树的最少节点与层数的关系是a1=1,a2=2,an = an-1+an-2+1
 *
 *
 *
 * */
class BalancedTree : public SearchTree {
public:
    void insert(int value){
        root = insertRecursive(root, value);
    }
    TreeNode* tree_get(){
        return root;
    }
private:
    TreeNode* insertRecursive(TreeNode * node,int value){
        if(node== nullptr){
            return  new TreeNode(value);
        }
        if(value<node->val){
            node->left = insertRecursive(node->left,value);
        }else{
            node->right = insertRecursive(node->right,value);
        }
        //平衡操作
        //
        /*
         *平衡因子为 -2：表示右子树高度比左子树高度大 2。此时需要进行左旋操作
          平衡因子为 -1：表示右子树高度比左子树高度大 1。此时需要左右旋操作
          平衡因子为 1：表示左子树高度比右子树高度大 1。此时需要右左旋操作
          平衡因子为 2：表示左子树高度比右子树高度大 2。此时需要右旋操作
         * */
        int balanceFactor = getBalanceFactor(node);
        if(balanceFactor>1&&value<node->left->val){//右旋操作
            return rotateRight(node);
        }
        if (balanceFactor < -1 && value > node->right->val) {//左旋操作
            return rotateLeft(node);
        }
        if (balanceFactor > 1 && value > node->left->val) {//左右旋操作
            /**左右旋操作：用于处理平衡因子为 -1 的情况。通过先对当前节点的左子树进行左旋操作，再对当前节点进行右旋操作，可以使得树恢复平衡。**/
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        if (balanceFactor < -1 && value < node->right->val) {//右左旋操作
            /**右左旋操作：用于处理平衡因子为 1 的情况。通过先对当前节点的右子树进行右旋操作，再对当前节点进行左旋操作，可以使得树恢复平衡。**/
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }
    int getBalanceFactor(TreeNode* node) {
        if(node == nullptr){
            return 0;
        }
        return getHeight(node->left)-getHeight(node->right);
    }
    TreeNode* rotateRight(TreeNode* node) {
        /**右旋操作：用于处理平衡因子为 2 的情况。通过右旋操作，可以将当前节点的左子树变为新的根节点，原根节点成为新根节点的右子树，新根节点的右子树成为原根节点的左子树 **/
        TreeNode* newRoot = node->left;
        TreeNode* subtree = newRoot->right;
        newRoot->right = node;
        node->left = subtree;
        return newRoot;
    }
    TreeNode* rotateLeft(TreeNode* node) {
        /** 左旋操作：用于处理平衡因子为 -2 的情况。通过左旋操作，可以将当前节点的右子树变为新的根节点，
         * 原根节点成为新根节点的左子树，新根节点的左子树成为原根节点的右子树。**/
        TreeNode* newRoot = node->right;
        TreeNode* subtree = newRoot->left;

        newRoot->left = node;
        node->right = subtree;

        return newRoot;
    }
};